//
// Created by 高森森 on 2022/2/15.
//

#ifndef LEETCODE_SOLUTION47_H
#define LEETCODE_SOLUTION47_H
#include<iostream>
using namespace std;
#include<vector>
#include<unordered_map>
#include <algorithm>

class Solution47 {
public:
    const int P=100000;
    vector<int> countPairs(int n, vector<vector<int>>& edges, vector<int>& queries) {
        int m=queries.size();
        //记录度
        vector<int>io(n+1);
        //对度进行排序，用双指针求deq[a]+deq[b]>query的个数
        vector<int>ans(m,0);
        //使用map记录两条边之间相连的边的数目
        unordered_map<int,int>map;
        for(auto &edge:edges){
            //为了防止重边，如【1，2】和【2，1】这种边
            int u=min(edge[0],edge[1]);
            int v=max(edge[0],edge[1]);
            io[u]++;
            io[v]++;
            int key=u*P+v;
            map[key]++;
        }
        vector<int>arr(io.begin(),io.end());
        sort(arr.begin(),arr.end());
        for(int i=0;i<m;i++)
        {
            int l=1;
            int r=n;
            while(l<r){
                while(l<r&&arr[l]+arr[r]<=queries[i])
                    l++;
                if(l<r)
                {
                    ans[i]+=r-l;
                }
                r--;
            }
            if(ans[i]==0)
                continue;
            for(auto it=map.begin();it!=map.end();it++){
                auto[key,connect]=*it;
               int u=key/P;
               int v=key%P;
               if(io[u]+io[v]>queries[i]&&io[u]+io[v]-connect<=queries[i])
               {
                   ans[i]--;
               }
            }
        }
        return ans;
    }
};


#endif //LEETCODE_SOLUTION47_H
